1. Field of the Invention
The present invention relates to test pattern compression applicable to fault detection of logic circuits and more particularly, to a system, a method, and a computer program product for compressing a test pattern set, which is applicable to fault detection of logic circuits.
2. Description of the Related Art
A test pattern set used for fault detection of logic circuits includes redundant test patterns and thus, xe2x80x9ctest pattern set compressionxe2x80x9d has been usually employed to decrease the number of test patterns included in a test pattern set without lowering the fault coverage.
To perform the xe2x80x9ctest pattern set compressionxe2x80x9d, reverse order fault simulation, undefined value assignment to random numbers, and test pattern merging have ever been combined together and used. The reverse order fault simulation is as follows.
First, the initial order of test patterns included in a test pattern set for a logic circuit to be tested (i.e., a target logic circuit) is reversed, forming order-reversed test patterns in the set. Then, the operation of the target logic circuit is simulated using the order-reversed test patterns, specifying unnecessary test patterns in the set. Finally, the unnecessary patterns thus specified are removed or deleted from the set, resulting in compression of the set. The reverse order fault simulation is disclosed in, for example, a paper written by Michael H. Schultz et al., IEEE Trans. On CAD, pp. 126-137, January 1988, xe2x80x9cSOCRATES: A HIGHLY EFFICIENT AUTOMATIC TEST PATTERN GENERATION SYSTEMxe2x80x9d.
FIG. 1 is a functional block diagram showing a prior-art test pattern set generator having a test pattern set compression system 700. The test pattern set generator in FIG. 1 comprises circuit/fault information input means 701, initial test pattern generating means 702, the test pattern set compression system 700, and test pattern output means 707. The test pattern set compression system 700 includes test pattern order reversing means 703, undefined value sensitizing means 704, test pattern removing/undefined value setting means 705, and test pattern merging means 706.
The circuit/fault information input means 701 fetches the information on the configuration and faults of the target logic circuit from the outside of the generator and the, sends it to the initial test pattern generating means 702. The information on the configuration and faults of the target logic circuit is termed the xe2x80x9ccircuit/fault information CFIxe2x80x9d below.
The initial test pattern generating means 702 generates an initial test pattern set TPS0 (i.e., a test pattern set to be compressed) on the basis of the circuit/fault information CFI thus received. Then, the means 702 sends the initial test pattern set TPS0 thus generated to the test pattern order reversing means 703. The initial test pattern set TPS0 includes specific test patterns. Each of the patterns includes specific input signals applicable to the target logic circuit.
The test pattern order reversing means 703 reverses the order of the test patterns included in the initial test pattern set TPS0. Alternately, the means 703 reverses the order of the test patterns included in a fourth test pattern set TPS4 sent from the test pattern merging means 706 explained later. Thus, due to the order-reversing operation, the initial test pattern set TPS0 or the fourth test pattern set TPS 4 is converted to a first test pattern set TPS1. Then, the means 703 sends the first test pattern set TPS1 thus generated to the undefined value sensitizing means 704.
The undefined value sensitizing means 704 assigns the value of xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d (i.e., a low- or high-level logic signal) to the input signals of the respective test patterns in the first test pattern set TPS1 thus received. In other words, the undefined values of xe2x80x9cXxe2x80x9d contained in the set TSP1 are sensitized. Due to this sensitization of the undefined values, the set TSP1 is converted to a second test pattern set TPS2. The means 704 sends the second test pattern set TPS2 thus obtained to the test pattern removing/undefined value setting means 705. The sensitization of undefined values eliminates the undefined logic states in the target logic circuit when simulation is carried out and therefore, there arises a possibility that any other faults are detected.
The test pattern removing/undefined value setting means 705 extracts successively the test patterns included in the second test pattern set TPS2 thus received according to the order of the test patterns and then, simulation operations are successively carried out using the test patterns thus extracted. The means 705 identifies or specifies unnecessary test patterns from all the test patterns included in the second set TPS2 on the basis of the simulation result. If at least one unnecessary pattern is identified by the means 705, the at least one unnecessary test pattern thus identified is removed from the set TPS2. Also, the means 705 sets undefined values on the unnecessary input signals of the remaining test patterns in the set TPS2, respectively, thereby facilitating the test pattern merging. Thus, the second test pattern set TPS2 is converted to a third test pattern set TPS3. The set TPS3 thus formed is sent to the test pattern merging means 706.
The test pattern merging means 706 identifies two or more mergible test patterns from the test patterns in the third test pattern set TPS3 thus received. Then, the means 706 merges the two or more test patterns thus identified together to form a single test pattern, thereby converting the set TPS3 to a fourth test pattern set TPS4. The set TPS4 thus generated corresponds to the compressed one of the initial test pattern set TPS0.
Moreover, the test pattern merging means 706 makes a judgment whether or not the fourth test pattern set TPS4 should be further compressed under a predetermined condition. If the means 706 judges further compression necessary, the means 706 returns the set TPS4 to the test pattern order reversing means 703 and then, the means 703, 704, 705, and 706 compresses the set TPS4 again in the same way as performed for the initial test pattern set TPS0. If the means 706 judges further compression unnecessary, the means 706 sends the set TPS4 to the test pattern output means 707.
The test pattern output means 707 sends the fourth test pattern set TPS4 thus received to the outside of the prior-art test pattern set generator of FIG. 1 as a finally-compressed test pattern set CTPS.
The undefined value identification operation by the test pattern removing/undefined value setting means 705 and the test pattern merging operation by the test pattern merging means 706 may be performed by any known technique, for example, disclosed in the Japanese Non-Examined Patent Publication No. 8-212799 published in August 1996.
In the prior-art test pattern compression system 700, the operations of the test pattern order reversing means 703, the undefined value sensitizing means 704, the test pattern removing/undefined value setting means 705, and the test pattern merging means 706 are repeated until all the mergeable test patterns are merged. As a result, the number of the test patterns constituting the initial test pattern set TPPS0 is decreased, in other words, the set TPS0 is compressed.
With the prior-art test pattern compression system 700 in FIG. 1, the fault simulation is carried out while reversing the order of the test patterns in the initial test pattern set TPS0. Thus, the patterns unnecessary to fault detection (i.e., that are removable) are easily identified. Moreover, since the test pattern merging is performed while undefined values are assigned to the input signals necessary to fault detection, the unnecessary test patterns are easily merged. Thus, the test pattern compression function can be enhanced.
However the prior-art test pattern compression system 700 has the following disadvantages.
The first disadvantage of the system 700 is that the test pattern compression performance (e.g., compressibility) varies dependent on the order of the test patterns in the initial test pattern set TPS0. The second disadvantage of the system 700 is that unnecessary test patterns to fault detection in the initial test pattern set TPS0 are difficult to be identified due to side effects of the reverse order fault simulation and the random number assignment to the undefined values.
The first disadvantage of the system 700 is explained in detail below with reference to FIGS. 2A to 2C that show the relationship between the test patterns and the detectable faults in the fault simulation.
Here, it is supposed that a logic circuit to be simulated (i.e., a target logic circuit) includes four faults A, B, C, and D, in which a test pattern A is designed to detect the faults A and B, a test pattern B is designed to detect the faults A and C, and a test pattern C is designed to detect the faults C and D.
As shown in FIG. 2A, a test pattern set 801 includes the test patterns a, B, and C that are arranged in this order. When a fault simulation operation of the target logic circuit is carried out using the set 801, the test pattern A is used first. Thus, the faults A and B are detected, as shown by the arrows a1 and a2. The faults A and B thus detected are removed from the target faults.
Next, a fault simulation operation using the test pattern B is carried out and as a result, the fault C is detected, as shown by the arrow a3. The fault C thus detected is removed from the target faults. The fault B, which has already been removed from the target faults, may be detected in this operation using the test pattern B. This is shown by a broken line in FIG. 2A, which is applied to the following cases explained later.
Furthermore, a fault simulation operation using the test pattern C is carried out and as a result, the fault D is detected, as shown by the arrow a4. The fault D thus detected is removed from the target faults. The fault C, which has already been removed from the target faults, may be detected in this operation using the test pattern C. This is shown by a broken line in FIG. 2A.
As described above, when the test pattern set 801 in FIG. 2A is used, all the faults a, B, C, and D are unable to be detected until the fault simulation operations using the test patterns A, B, and C are completed. In other words, to detect all the faults A, B, C, and D, all the patterns A, B, and C are necessarily used for simulation. As a result, none of the patterns A, B, and C can be removed when the set 801 is used.
FIG. 2B shows a test pattern set 802 that includes the test patterns C, B, and A arranged in this order. The set 802 corresponds to one obtained by reversing the order of the test patterns A, B, and C in the set 801 of FIG. 2A.
First, a fault simulation operation using the test pattern C is carried out and as a result, the faults C and D are detected, as shown by the arrows b1 and b2. The faults C and D are removed from the target faults.
Next, a fault simulation operation using the test pattern B is carried out and the fault A is detected, as shown by the arrow b3. The fault A is removed from the target faults.
Finally, a fault simulation operation using the test pattern A is carried out and the fault B is detected, as shown by the arrow b4. The fault B is removed from the target faults.
As described above, when the test pattern set 802 in FIG. 2B is used, all the faults A, B, C, and D are unable to be detected until the fault simulation operations using the test patterns C, B, and A are completed. This is the same as the case using the test pattern set 801. As a result, none of the patterns A, B, and C can be removed when the set 802 is used.
FIG. 2C shows a test pattern set 803 that includes the test patterns C, A, and B arranged in this order. When the set 803 is used, unlike the above two cases using the sets 801 and 802, unnecessary test patterns can be identified.
First, a fault simulation operation using the test pattern C is carried out and as a result, the faults C and D are detected, as shown by the arrows c1 and c2. The faults C and D are excluded from the target faults.
Next, a fault simulation operation using the test pattern A is carried out and the faults A and B are detected, as shown by the arrows c3 and c4. The faults A and B are excluded from the target faults. At this time, all the faults A, B, C, and D can be detected. Thus, the pattern B is identified as an unnecessary pattern and can be removed from the target faults when the set 803 is used.
As seen from the above explanation using the test pattern sets 801, 802, and 803 in FIGS. 2A to 2C, unnecessary test patterns can be or cannot be identified according to the order difference of the test patterns A, B, and C in the sets 801, 802, and 803. Also, as seen from the cases using the sets 801 and 802 in FIGS. 2A and 2B, unnecessary test patterns are difficult to be identified by simply reversing the order of the patterns A, B, and C. In other words, there is a possibility that unnecessary patterns cannot be identified even if fault simulation operations are performed while reversing the order of the patterns A, B, and C. Whether or not unnecessary patterns are identified is determined dependent on the order of the patterns in the initial test pattern set TPS0. Thus, the compression performance of a test pattern set varies dependent on the order of the test patterns in the set that are generated by the initial test pattern generating means 702.
The second disadvantage of the prior-art test pattern compression system 700 due to the side effects of the reverse order fault simulation and the random number assignment to the undefined values is explained in detail below with reference to FIGS. 3A to 3D.
As already explained above, when the initial test pattern set TPS0 is sent from the initial test pattern generating means 702 to the test pattern order reversing means 703, the reversing means 703 reverses the order of the test patterns contained in the set TPS0 to form the first test pattern set TPS1 and then, the means 703 sends the set TPS1 thus formed to the undefined value sensitizing means 704. The means 704 sensitizes the undefined values in the set TPS1 to form the second test pattern set TPS2 and then, sends the set TPS2 to the test pattern removing/undefined values setting means 705.
At this time, it is supposed that the second test pattern set TPS2 sent from the undefined value sensitizing means 704 is a test pattern set 901 as shown in FIG. 3A. The set 901 contains n test patterns 1, 2, . . . , and n that are arranged in this order. The test pattern removing/undefined values setting means 705 successively carried out fault simulation operations using the patterns 1, 2, . . . , and n in the set 901.
FIG. 3A shows the number of detectable faults in the fault simulation operations using the set 901 and the number of undefined values before sensitization by the means 704. Here, it is supposed that the numbers of detectable faults in the simulation operations using the test patterns 1, 2, . . . , and n are almost the same and that the numbers of undefined values before sensitization in the test patterns 1, 2, . . . , and n are almost the same.
In the fault simulation operation using the first test pattern 1 in the set 901, a lot of faults are detected and removed from the target faults. Thus, in the fault simulation operation using the second test pattern 2, the number of the detected faults is smaller than that in the operation using the pattern 1. Similarly, in the fault simulation operation using the third test pattern 3, the number of the detected faults is smaller than that in the operation using the pattern 2. Thus, the number of the detected faults is minimized in the operation using the n-th pattern n.
Also, the test pattern removing/undefined values setting means 705 sets undefined values on the unnecessary input signals to fault detection according to the result of the fault simulation operations. As the number of the detected faults becomes larger, the number of the input signals on which the undefined values are set increases and at the same time, the number of the undefined values increases.
Accordingly, the third test pattern set TPS3 obtained by setting the undefined values is given by a test pattern set 902 shown in FIG. 3B. In the set 902, as seen from FIG. 3B, the number of the undefined values becomes larger and the number of the detectable faults becomes smaller according to the ascending order of the test patterns 1xe2x80x2 to nxe2x80x2.
When the third test pattern set TPS3 (i.e., the test pattern set 902) is sent to the test pattern merging means 806, the means 706 merges the test patterns included in the set 902 as much as possible, forming the fourth test pattern set TPS4. The test pattern output means 707 sends the set TPS4 thus formed to the test pattern order reversing means 703 if further compression is needed. The means 703 reverses the order of the test patterns in the set TPS4 to form the first test pattern set TPS1 and then, it sends the set TPS1 thus formed to the undefined value sensitizing means 704. The means 704 sensitizes the undefined values in the set TPS1 to form the second test pattern set TPS2 and then, it sends the set TPS2 thus formed to the test pattern removing/undefined value setting means 705.
At this time, the second test pattern set TPS2 has the reversed order of the test patterns with respect to the test pattern set 902 of FIG. 3B, resulting in a test pattern set 903 including the test patterns nxe2x80x2 to 1xe2x80x2 arranged in this order, as shown in FIG. 3C. The test pattern removing/undefined value setting means 705 performs the fault simulation operations using the patterns nxe2x80x2 to 1xe2x80x2 in the set 903.
The number of the undefined values shown in FIG. 3C is a number before the undefined value sensitizing means 704 sensitizes the undefined values.
When the fault simulation operations are performed by the test pattern removing/undefined value setting means 705 using the test pattern set 903, the same result as that in the case using the test pattern set 901 of FIG. 3A is given. Specifically, in the fault simulation operation using the first test pattern nxe2x80x2, the number of the detectable faults is maximized. The number of the detectable faults decreases according to the descending order of the patterns (nxe2x88x921) to 1. The more the faults are detected in the fault simulation operations, the more the input signals are set as undefined values and the higher the number of the undefined values becomes.
On the other hand, in the test pattern set 903, the umber of the undefined values increases and the number of the detectable faults decreases with the descending order of the patterns nxe2x80x2 to 1xe2x80x2. Thus, the third test pattern set TPS3 given by setting the undefined values is given by a test pattern set 904 including the test patterns nxe2x80x3 to 1xe2x80x3 arranged in this order, as shown in FIG. 3D. As seen from FIG. 3D, in the set 904, the numbers of the detectable faults in the patterns nxe2x80x3 to 1xe2x80x3 are almost the same and the numbers of the undefined values in the test patterns nxe2x80x3 to 1xe2x80x3 are almost the same.
Paying attention to the numerical change of the detectable faults in the patterns n, nxe2x80x2, and nxe2x80x3, the numerical change has a tendency to vary like xe2x80x9cmediumxe2x86x92smallxe2x86x92smallxe2x86x92smallxe2x86x92mediumxe2x80x9d. The same tendency appears when the compression operation by the compression system 700 is further repeated. Thus, the test patterns with the number of the detectable faults being xe2x80x9c0xe2x80x9d are difficult to be generated and as a result, the unnecessary test patterns are difficult to be identified.
As explained above, with the prior-art test pattern set compression system 700 in FIG. 1, there is a problem that the test pattern compression performance varies dependent on the order of the test patterns contained in the initial test pattern set TPS0. Also, there is another problem that the unnecessary test patterns to fault detection in the set TPS0 are difficult to be identified. Thus, the compression performance is not satisfactorily high.
Accordingly, an object of the present invention is to provide a system, a method, and a computer program product for compressing a test pattern set for a logic circuit that eliminates the above-described problems in the prior-art test pattern set compression system.
Another object of the present invention is to provide a system, a method, and a computer program product for compressing a test pattern set for a logic circuit that compresses efficiently (i.e., at high compressibility) the test pattern set.
Still another object of the present invention is to provide a system, a method, and a computer program product for compressing a test pattern set for a logic circuit that compresses the test pattern set at high speed.
The above objects together with others not specifically mentioned will become clear to those skilled in the art from the following description.
According to a first aspect of the present invention, a system for compressing a test pattern set including test patterns arranged in a specific order to detect faults in a logic circuit is provided, which is comprised of:
(a) a test pattern rearranger subsystem that rearrange the test patterns included in the test pattern set to be in ascending order of a number of undefined values included in each of the patterns;
(b) an undefined value sensitizer subsystem that assigns a defined value to the respective undefined values included in each of the patterns, sensitizing the patterns;
(c) a test pattern remover subsystem that removes a fault-undetectable pattern or patterns from the patterns to which the defined value or values has/have been assigned by the undefined values sensitizer subsystem;
(d) an undefined value setter subsystem that sets undefined values to a parameter in each of the patterns unnecessary to fault detection; and
(e) a test pattern merger subsystem that merges fault-detectable patterns included in the set that have not been removed by the test pattern remover subsystem according to a specific rule.
With the system for compressing a test pattern set according to the first aspect of the present invention, the test pattern set for the logic circuit can be compressed efficiently (i.e., at high compressibility) and/or at high speed due to the following reason.
Generally, as the number of undefined values included in a test pattern for a logic circuit decreases, the number of detectable faults in a testing operation using one of the test patterns in the set becomes larger. This fact was found by the inventor. Thus, the number of the faults that can be removed or excluded in a testing operation using one of the test patterns in the set increases with the decreasing number of undefined values in the pattern used for the testing operation. Taking this fact into consideration, with the system according to the first aspect of the invention, the test pattern rearranger subsystem is provided to rearrange the order of the test patterns included in the test pattern set so as to be in ascending order of the number of the undefined values included in each of the patterns.
Also, since the order of the test patterns included in the set is rearranged so as to be in ascending order of the number of the undefined values included in each of the patterns, the patterns with a larger number of the undefined values are used for later testing operations. Thus, these patterns tend to be easily merged with other pattern or patterns in the set by the test pattern merger subsystem.
Accordingly, the latter one of the patterns in the set is used for a testing operation, the less the number of the patterns in the set becomes, which means that the patterns in the set can be compressed efficiently or at high compressibility.
Moreover, a test pattern with less undefined values detects more faults than a test pattern with more undefined values. As a result, the latter the testing operation is performed, the shorter the time necessary to fault detection becomes, thereby decreasing the total time necessary to overall fault detection. Thus, the compression of the test pattern set can be carried out at high speed.
In a preferred embodiment of the system according to the first aspect of the invention, the rearranger subsystem rearranges the term patterns in the test pattern set using random numbers.
In another preferred embodiment of the system according to the first aspect of the invention, the rearranger subsystem rearranges the test patterns in the test pattern set using random numbers when no order change of the patterns in the set occurs according to rearrangement in ascending order of the number of undefined values, or an order change of the patterns in the set occurring according to rearrangement in ascending order of the number of undefined values is equal to or less than a specific threshold value. In this embodiment, there is an additional advantage to avoid the situation that no patterns is removed even if random numbers are used.
In still another preferred embodiment of the system according to the first aspect of the invention, the rearranger subsystem rearranges an additional rearrangement operation to the patterns merged by the test pattern merger subsystem after a rearrangement operation.
In a further preferred embodiment of the system according to the first aspect of the invention, there are further provided with a circuit/fault information input subsystem that inputs circuit information and fault information on the logic circuit; and a test pattern set generator subsystem that generates the test pattern set according to the circuit information and the fault information thus inputted. In this embodiment, the rearranger subsystem can rearrange any of the test pattern sets generated by the test pattern set generator subsystem.
According to a second aspect of the present invention, a method for compressing a test pattern set including test patterns arranged in a specific order to detect faults in a logic circuit is provided, which is comprised of:
(a) rearranging the order of the test patterns included in the test pattern to be in ascending order of a number of undefined values included in each of the patterns;
(b) assigning a defined value to the respective undefined values included in each of the patterns, sensitizing the undefined values;
the patterns with the sensitized undefined values containing a fault-undetectable pattern or patterns and a fault-detectable pattern or patterns for the logic circuit;
(c) removing the fault-undetectable pattern or patterns from the set;
(d) assigning an undefined values to a parameter unnecessary to fault detection in the fault-detectable pattern or patterns; and
(e) merging some of the fault-detectable patterns that are mergeable together according to a specific rule.
With the method for compressing a test pattern set according to the second aspect of the invention, because of substantially the same reason as described in the system according to the first aspect of the invention, the test pattern sets for the logic circuit can be compressed efficiently (i.e., at high compressibility) and/or at high speed.
In a preferred embodiment of the method according to the second aspect of the invention, the step (a) of rearranging the order of the test patterns is performed by rearranging the test patterns in the set using random numbers.
According to a third aspect of the present invention, a computer program product having a computer readable medium and a computer program recorded thereon is provided, the computer program being operable to compress a test pattern set including test patterns arranged in a specific order to detect faults in a logic circuit, which is comprised of:
(a) code that rearranges the order of the test patterns included in the test pattern to be in ascending order of a number of undefined values included in each of the patterns;
(b) code that assigns a defined value to the respective undefined values included in each of the patterns, sensitizing the undefined values;
the patterns with the sensitized undefined values containing a fault-undetectable pattern or patterns and a fault-detectable pattern or patterns for the logic circuit;
(c) code that removes the fault-undetectable pattern or patterns from the set;
(d) code that assigns an undefined value to a parameter unnecessary to fault detection in the fault-detectable pattern or patterns; and
(e) code that merges some of the fault-detectable patterns that are mergeable together according to a specific rule.
With the product according to the third aspect of the present invention, because of substantially the same reason as described in the system according to the first aspect of the invention, the test pattern sets for logic circuits can be compressed efficiently (i.e., at high compressibility) and/or at high speed.
In a preferred embodiment of the product according to the third aspect of the invention, the code (a) that rearranges the order of the test patterns is performed by rearranging the test patterns in the set using random numbers.